package seqlist.doubleList;


class DoubleNodeTest{
    public static void main(String[] args) {
        DoubleList doubleList = new DoubleList();
        doubleList.addHead(3);
        doubleList.addHead(2);
        doubleList.addHead(1);
        doubleList.addTail(4);
        doubleList.addTail(6);
        doubleList.addTail(6);
        doubleList.addTail(6);
        doubleList.addIndex(5,5);
        System.out.println("插入");
        System.out.println(doubleList.toString());
        doubleList.delNode(1);
        System.out.println("删除");
        doubleList.delNodeAllVal(6);
        doubleList.delNode(0);
        System.out.println(doubleList.toString());
        System.out.println("修改");
        doubleList.update(1,2);
        System.out.println(doubleList.toString());
        System.out.print("查询:");
        DoubleNode search = doubleList.search(4);
        System.out.println("下表为4的节点值为："+search.val);
    }
}

public class DoubleList {
    private int size;
    private DoubleNode head;
    private DoubleNode tail;
    //头插入
    public void addHead(int val){
        DoubleNode node = new DoubleNode(null,head,val);
        if (tail == null){
            tail = node;
        }else {
            head.prev = node;
        }
        head = node;
        size++;
    }
    //尾插
    public void  addTail(int val){
        DoubleNode node = new DoubleNode(tail,null,val);
        if (head == null){
            head = node;
        }else {
            tail.next = node;
        }
        tail = node;
        size++;
    }
    //按索引插入
    public void addIndex(int val,int index){
        if (index < 0 || index > size){
            System.err.println("index 不合法");
            return;
        }
        if (index == 0){
            addHead(val);
        }else if (index == size-1){
            addTail(val);
        }else {
            DoubleNode preNode = search(index - 1);
            DoubleNode temp = preNode.next;
            DoubleNode node = new DoubleNode(preNode,temp,val);
            temp.prev = node;
            preNode.next = node;
            size++;
        }
    }
    //删除按下标
    public void delNode(int index){
        DoubleNode node = search(index);
        delNode(node);
    }
    //删除按第一个值为val的节点
    public void deNodeByVal(int val){
        DoubleNode cur = head;
        while (cur.val != val){
            cur = cur.next;
        }
        delNode(cur);
    }
    //删除所有值为val的节点
    public void delNodeAllVal(int val){
        DoubleNode node = head;
        while (node != null){
            if (node.val == val){
                DoubleNode temp = node.next;
                delNode(node);
                node = temp;
            }else {
                node = node.next;
            }
        }
    }
    //删除按节点
    public  void  delNode(DoubleNode node){
        DoubleNode preNode = node.prev;
        DoubleNode lastNode = node.next;

        if (preNode == null){
            head = lastNode;
        }else {
            preNode.next = lastNode;
            node.prev = null;
        }

        if (lastNode == null){
            tail = preNode;
        }else {
            lastNode.prev = preNode;
            node.next = null;
        }
        size--;
    }
    //修改
    public void update(int index,int val){
        DoubleNode node = search(index);
        node.val = val;
    }
    //查询按下标
    public DoubleNode search(int index){
        DoubleNode node = null;
        if (index > size / 2){
            node = tail;
            for (int i = size; i > index ; i--) {
                node = node.prev;
            }
        }else {
            node = head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        }
        return node;
    }

    //toString
    public String toString(){
        String ret = "";
        DoubleNode temp = head;
        while (temp != null){
            ret += temp.val;
            ret += "->";
            temp = temp.next;
        }
        ret += null;
        return ret;
    }
}

class DoubleNode{
    DoubleNode prev;
    DoubleNode next;
    int val;

    public DoubleNode() {
    }

    public DoubleNode(DoubleNode prev, DoubleNode next, int val) {
        this.prev = prev;
        this.next = next;
        this.val = val;
    }
}